#include "BinaryTree.h"
#include "Queue.h"
BTNode* BinaryTreeCreate(BTDataType* a, int* pi, int n)
{
	if (*pi >= n)
	{
		return NULL;
	}
	if (a[(*pi)] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = (BTNode*)malloc(sizeof(BTNode));
	root->data = a[(*pi)++];
	root->left = BinaryTreeCreate(a, pi, n);
	root->right = BinaryTreeCreate(a, pi, n);
	return root;
}

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	free(root);
}

void BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("#");
		return;
	}
	printf("%c", root->data);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

void BinaryTreeInOrder(BTNode* root)
{
	
	if (root == NULL)
	{
		printf("#");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c",root->data);
	BinaryTreeInOrder(root->right);
}

void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("#");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c",root->data);
}

int BinaryTreeSize(BTNode* root)
{
	return root == NULL ? 0 : 
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->left, k - 1) 
		+ BinaryTreeLevelKSize(root->right, k - 1);
}

int BinaryTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;

	int leftHeight = BinaryTreeHeight(root->left);
	int rightHeight = BinaryTreeHeight(root->right);
	return leftHeight > rightHeight ? 
		leftHeight + 1 : rightHeight + 1;
}

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* rootLeft = BinaryTreeFind(root->left, x);
	if (rootLeft)
		return rootLeft;
	BTNode* rootRight = BinaryTreeFind(root->right, x);
	if (rootRight)
		return rootRight;
	return NULL;
}

void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);

		printf("%c",front->data);
		if (front->left)
			QueuePush(&q,front->left);

		if (front->right)
			QueuePush(&q, front->right);

	}
	QueueDestroy(&q);
}

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
		QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
			break;
		QueuePush(&q, front->left);
		QueuePush(&q, front->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front)
		{
			QueueDestroy(&q);
			return false;

		}
	}
	QueueDestroy(&q);
	return true;
}
